package com.weave.tree;

import java.util.Comparator;

/**
 * @Description
 * Balanced Binary Search Tree，平衡二叉搜索数
 * 将旋转操作封装起来，写在一套代码里太冗余
 * @Author weave
 * @Date 2023/11/14 20:32
 */
public class BBST<E> extends BST<E>{
    public BBST(){
        this(null);
    }

    public BBST(Comparator<E> comparator){
        super(comparator);
    }

    /**
     * 左旋
     * @param grand 高度最低的不平衡结点
     */
    protected void rotateLeft(Node<E> grand){
        Node<E> parent = grand.right;
        Node<E> child = parent.left;
        grand.right = child;
        parent.left = grand;
        afterRotate(grand,parent,child);
    }

    /**
     * 右旋
     * @param grand 高度最低的不平衡结点
     */
    protected void rotateRight(Node<E> grand) {
        Node<E> parent = grand.left;
        Node<E> child = parent.right;
        grand.left = child;
        parent.right = grand;
        afterRotate(grand, parent, child);
    }

    /**
     * 规律旋转，a和g保持原样不动
     * @param r 子树的根节点
     * @param b 做为d的左结点
     * @param c 做为b的右结点
     * @param d 原来的d在这个时候做为根节点
     * @param e 做为f的左结点
     * @param f 做为d的右结点
     */
    protected void rotate(Node<E> r, Node<E> b, Node<E> c, Node<E> d, Node<E> e, Node<E> f) {
        // 让d成为这棵子树的根节点
        d.parent = r.parent;
        if (r.isLeftChild()) {
            r.parent.left = d;
        } else if (r.isRightChild()) {
            r.parent.right = d;
        } else {
            root = d;
        }

        //b-c
        b.right = c;
        if (c != null) {
            c.parent = b;
        }

        // e-f
        f.left = e;
        if (e != null) {
            e.parent = f;
        }

        // b-d-f
        d.left = b;
        d.right = f;
        b.parent = d;
        f.parent = d;

    }

    /**
     * 旋转之后，更新各个结点的parent
     * @param grand 原来的grand结点
     * @param parent 原来的parent结点
     * @param child parent的左结点
     */
    protected void afterRotate(Node<E> grand, Node<E> parent, Node<E> child) {
        // parent成为子树的根节点
        parent.parent = grand.parent;
        if(grand.isLeftChild()){
            grand.parent.left = parent;
        }else if(grand.isRightChild()){
            grand.parent.right = parent;
        }else{
            root = parent;
        }

        // 更新child的parent
        if(child != null){
            child.parent = grand;
        }

        // 更新grand的parent
        grand.parent = parent;
    }
}
